package com.zklh.leetcode.other.problem22;

import java.util.*;

class Solution {

    /*public List<String> generateParenthesis(int i){
        Set<String> resultSet = new HashSet<>();
        parenthesisExtend(resultSet,new StringBuilder("()"),i-1);
        List<String> result = new ArrayList<>();
        result.addAll(resultSet);
        return result ;
    }

    /**
     * 扩充括号方法
     * @param originParenthesis 要进行扩充的括号字符串
     * @param remainNum 当前剩余的要扩充的括号
     */
    /*private void parenthesisExtend(Set<String> result,StringBuilder originParenthesis, int remainNum){
        if(remainNum == 0){
            result.add(originParenthesis.toString());
            return;
        }
        originParenthesis.append(")");
        for (int i = 0; i < originParenthesis.length(); i++) {
            if(originParenthesis.charAt(i) == ')'){
                parenthesisExtend(result,new StringBuilder(originParenthesis.toString()).insert(i,'('),remainNum-1);
            }
        }
    }*/


    /*public List<String> generateParenthesis(int i){
        Set<String> resultSet = new HashSet<>();
        List<String> list = new ArrayList<>();
        parenthesisExtend(list,new char[]{'(',')'},i);

        *//*list.addAll(resultSet);*//*
        return list ;
    }

    *//**
     * 递归在字符左右两边增加()的方式, 实现
     * @param //result
     * @param //chars
     * @param //num
     *//*
    public void parenthesisExtend(List<String> result, char[] chars,int num){
        if(chars.length == num * 2){
            result.add(new String(chars));
            return;
        }
        // 标记是否chars 为 ()()()()
        boolean flag = true;
        for (int i = 0; i < chars.length-1; i++) {
            if(chars[i] == chars[i + 1]){
                flag = false;
            }
        }
        if(flag){
            // 表示左插入括号
            char[] chars1 = new char[chars.length + 2];
            // 表示环插入括号
            char[] chars2 = new char[chars.length + 2];
            chars1[0] = '(';
            chars1[1] = ')';
            chars2[0] = '(';
            chars2[chars2.length-1] = ')';
            // 向两个数组填值
            for (int i = 0; i < chars.length; i++) {
                chars1[i+2] = chars[i];
                chars2[i+1] = chars[i];
            }
            parenthesisExtend(result,chars2,num);
            parenthesisExtend(result,chars1,num);

        }else{
            // 表示左插入括号
            char[] chars1 = new char[chars.length + 2];
            // 表示环插入括号
            char[] chars2 = new char[chars.length + 2];
            // 表示右插入括号
            char[] chars3 = new char[chars.length + 2];
            chars1[0] = '(';
            chars1[1] = ')';
            chars2[0] = '(';
            chars2[chars2.length-1] = ')';
            chars3[chars3.length-2] = '(';
            chars3[chars3.length-1] = ')';
            // 向两个数组填值
            for (int i = 0; i < chars.length; i++) {
                chars1[i+2] = chars[i];
                chars2[i+1] = chars[i];
                chars3[i] = chars[i];
            }
            parenthesisExtend(result,chars2,num);
            parenthesisExtend(result,chars3,num);
            parenthesisExtend(result,chars1,num);
        }
    }*/


    public List<String> generateParenthesis(int i){
        List<String> result = new ArrayList<>();
        char[] chars = new char[i * 2];
        dfs(result,0,0,chars);
        return result;
    }


    /**
     * 利用深度优先搜索和回溯算法的原理, 实现生成()序列
     * @param result 用于存放满足条件的括号序列
     * @param blance 平衡, 这里blance = open - close , 如果小于0, 表示不平衡,直接返回
     * @param length 当前括号序列的长度, 对应当前添加的字符的索引
     * @param chars 存放括号字符, 字符在括号序列的先后顺序同索引一致
     */
    private void dfs(List<String> result, int blance, int length, char[] chars) {
        // 当前字符 '(' 数目 小于 ')' 则, 不可能有效, 直接返回, 回溯算法的体现
        if(blance < 0){
            return;
        }
        // 递归终止条件, 长度到达上限
        if(length == chars.length){
            //blance == 0 满足条件,表示( ) 数目相同, 则可以入库了
            if(blance == 0){
                result.add(new String(chars));
            }
            return;
        }

        // 添加左括号 blance++
        chars[length] = '(';
        dfs(result, blance+1,length+1,chars);

        // 添加右括号
        chars[length] = ')';
        dfs(result,blance-1,length+1,chars);
    }



    public static void main(String[] args){
        Solution solution = new Solution();
        List<String> result = solution.generateParenthesis(4);
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}
